package com.jiang.专题.动态规划.Q920;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/03/31 16:37
 */
public class Solution {
    public int numMusicPlaylists(int n, int goal, int k) {
        final int MOD = (int) (1e9 + 7);

        long[][] dp = new long[n + 1][goal + 1]; // dp[i][j]表示使用i个不同的歌曲播放j首歌曲的方案数
        dp[0][0] = 1; // 初始条件，使用0个不同的歌曲播放0首歌曲的方案数为1
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= goal; j++) {
                dp[i][j] += dp[i - 1][j - 1] * (n - i + 1);
                dp[i][j] += dp[i][j - 1] * Math.max(0, i - k);
                dp[i][j] %= MOD;
            }
        }
        return (int) dp[n][goal];
    }
}
